package code.c02_list.linkList;

import code.c02_list.linkList.LinkListClass;
import code.c02_list.clinkList.LinkNode;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/9/18 19:21
 * @package code.c02_list.classwork.examples
 * @description 有两个递增有序整数单链表A和B，假设每一个单链表中没有值相同的节点，但是两个单链表中存在
 * 相同值的节点，设计一个尽可能高效的算法建立一个新的递增有序整数单链表C，其中包含A和B相同值的节点，
 * 要求算法执行后不改变单链表A和B。
 */

public class Exam_2_17 {
    public static LinkListClass<Integer> commNodes(LinkListClass<Integer> A,LinkListClass<Integer> B){
        LinkNode<Integer> p = A.head.next;
        LinkNode<Integer> q = B.head.next;

        LinkListClass<Integer> C = new LinkListClass<>();

        LinkNode<Integer> t = C.head,s;
        while (p != null && q!= null){
            if (p.data < q.data){
                p = p.next;
            }else if (q.data < p.data){
                q = q.next;
            }else {
                s = new LinkNode<Integer>(p.data);
                t.next =s;
                t = s;
                p = p.next;
                q = q.next;
            }
        }

        t.next = null;
        return C;
    }
}
